/*
 * @lc app=leetcode.cn id=236 lang=javascript
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    let ans
    let dfs=function(root,p,q){
        if(!root)return false
        let lHaveSon=dfs(root.left,p,q)
        let RHaveSon=dfs(root.right,p,q)
        if((lHaveSon&&RHaveSon)||((root.val==p.val||root.val==q.val)&&(lHaveSon||RHaveSon))){
            ans=root
            return
        }
        return lHaveSon||RHaveSon||root.val==p.val||root.val==q.val
    }
    dfs(root,p,q)//此函数返回此节点以及其子节点是否包含P或者q
    return ans
};
// @lc code=end
//方法二  hash保存每个节点父节点，然后递归找p父节点标记，q找到有标记父节点，即可
